#ifndef _GRAPH_H
#define _GRAPH_H

#include <stdio.h>
#include <limits.h>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_set>

using namespace std;

const int ErrVal = -1;

struct GraphEdge;

struct GraphNode
{
    int value;//节点真实值，通常为题目给的节点编号
    int weight;//节点权重，用于最短路径搜索
    int in;
    int out;
    vector<GraphNode *> nexts;
    vector<GraphEdge *> edges;

    //用于Tarjin
    int dfn, low, child;
    bool inSt;
    GraphNode *parent;

    GraphNode(int v)
    {
        value = v;
        weight = INT_MAX;
        in = out = 0;
        dfn = low = -1;
        inSt = 0;
        parent = NULL;
    }
    GraphNode()
    {
        value = ErrVal;
        weight = INT_MAX;
        in = out = 0;
        dfn = low = -1;
        inSt = 0;
        parent = NULL;
    }
};

struct NodeCmp
{
    //less比较器，返回true则 a低于b
    bool operator()(const GraphNode* a, const GraphNode* b) const 
    {
        return a->weight > b->weight;
    }
};

struct GraphEdge
{
    int weight;//边权重
    GraphNode *from;
    GraphNode *to;

    GraphEdge(GraphNode* f, GraphNode *t, int w)
    {
        weight = w;
        from = f;
        to = t;
    }
};

struct EdgeCmp
{
    bool operator()(const GraphEdge* a, const GraphEdge* b) const
    {
        return a->weight > b->weight;
    }
};

struct Graph
{
    vector<GraphNode*> nodeSet;
    vector<GraphEdge*> edgeSet;

    Graph(int nodeCount)
    {
        nodeSet = vector<GraphNode*>(nodeCount);
        for (int i = 0; i < nodeCount; ++i)
        {
            nodeSet[i] = new GraphNode();
        }
        edgeSet = vector<GraphEdge *>();
    }
    ~Graph()
    {
        for (int i = 0; i < nodeSet.size(); ++i)
        {
            delete nodeSet[i];
        }
        for (int i = 0; i < edgeSet.size(); ++i)
        {
            delete edgeSet[i];
        }
    }
    void AddPath(int from, int to, int weight);
};

extern void Graph_DFS(Graph *g, int nodeIdx);

extern void Graph_BFS(Graph *g, int nodeIdx);

#endif